package _back_tracking

import org.junit.Assert
import org.junit.Test

/*
  93. 复原 IP 地址
  有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
  例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
  给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

示例 1：
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

示例 2：
输入：s = "0000"
输出：["0.0.0.0"]

示例 3：
输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

 */
class leetcode_93 {
    @Test
    fun test_1() {
        val actual = restoreIpAddresses("25525511135")
        val expect = arrayListOf("255.255.11.135", "255.255.111.35")
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    @Test
    fun test_2() {
        val actual = restoreIpAddresses("0000")
        val expect = arrayListOf("0.0.0.0")
        Assert.assertEquals(expect.toString(), actual.toString())
    }


    @Test
    fun test_3() {
        val actual = restoreIpAddresses("101023")
        val expect = arrayListOf("1.0.10.23", "1.0.102.3", "10.1.0.23", "10.10.2.3", "101.0.2.3")
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    fun restoreIpAddresses(s: String): List<String> {
        /*
        回溯法

        注意：
        1 合法的IP 数字
        #1 不能以0开头
        #2 不能非法数字
        #3 [0,255]
        #4 4个数，且数字全部用完
        #5 不能排序

        2 剪枝：
        数字的长度大于4剪掉，直接return

        3 先找出path，再组成IP更简单

        4 IP地址一共有4部分，深度是4
         */
        val path: ArrayList<String> = ArrayList<String>()
        val result: ArrayList<String> = ArrayList<String>()
        backtracking(s, 0, path, result)
        return result
    }

    private fun backtracking(s: String, startIndex: Int, path: ArrayList<String>, result: ArrayList<String>) {
        // 1 终止条件
        if (s.length == 0 || s.length < 4 || s.length > 12) { // 剪枝
            return
        }
        if (startIndex > s.length) {
            return
        }
        // 2 收集结果
        if (path.size == 4) {
            if (startIndex == s.length) { // 方法1:当指针移动到最后
                var ip: String = path[0]
                for (i in 1 until path.size) {
                    ip = ip + "." + path[i]
                }
                // 方法2:当指针移动到最后
                // 判断拼接后的大小 等于 s + 3 个点
//                if (str.length == (s.length + 3)) {
                result.add(ip)
                // println("collect, path=${path.toString()}, str=${str}")
//                }
            }
            return
        }

        // 3 单层循环
        for (i in startIndex until s.length) { // [startIndex, end index]
            // 4 处理节点：合法性
            val ip: String = s.substring(startIndex..i) // [startIndex, i]
            // println("for, ip=${ip}")
            // 处理节点
            if (!isValid(ip)) {
                return
            }
            path.add(ip)
            // println("for, ip=${ip},path=${path.toString()}")

            // 5 递归
            backtracking(s, i + 1, path, result)

            // 6 回溯
            path.removeAt(path.size - 1)
        }
    }

    fun isValid(node: String): Boolean {
        // 0+非0?
        if (node.length > 1 && node.startsWith("0")) {
            return false
        }

        var num: Int
        try {
            num = node.toInt()
        } catch (ex: Exception) {
            num = -1
        }
        // [0，255]?
        if (num < 0 || num > 255) {
            return false
        }
        return true
    }
}